3.2 
//The runtime is O(N);
//you are given a linked list, L , and another linked list, P, containing integers sorted in ascending order. 
//The operation PrintLots(L,P) will print the elements in L that are in positions specified by P. 
//For instance ,if P=1,3,4,6,the first ,third, fourth , and sixth elements in L are printed .
//Write the procedure PrintLots(L,P).You should use only the basic list operations. 
//What is the running time of your procedure?


void PrintLost(List *L, List *P)
{
    Position l = L, p = P;
    while(p->Next)
    {
        while(--p->Element)
        {
            if(l->Next==Null){
                printf("List L is at the end!\n");
                return;
            }
            l = l->Next;
        }
        printf("%d\n",l->Element);
    }
    return;
}






3.3a
//singly linked lists
void SinglySwap(List *L, ElementType Element1, List *P, ElementType Element2)
{
    //find the previous position of the required element
    Position l = FindPrevious( L, Element1);
    Position p = FindPrevious( P, Element2);
    Position TmpCell;
    TmpCell = l->Next;
    l->Next = p->Next;
    p->Next = TmpCell;
    TmpCell = l->Next->Next;
    l->Next->Next = p->Next->Next;
    p->Next->Next = TmpCell;
    return;
}
Position FindPrevious( List *P, ElementType Element )
{
    while(P->Next->Element!=Element)
        P = P->Next;
    return P;
}



3.3b
//doubly linked lists
void DoublySwap(List *L, ElementType Element1, List *P, ElementType Element2)
{
    Position l = FindPosition( L, Element1);
    Position p = FindPosition( P, Element2);
    Position TmpCell;
    TmpCell = l->Next;
    l->Next = p->Next;
    p->Next = TmpCell;
    TmpCell = l->Previous;
    l->Previous = p->Previous;
    P->previous = TmpCell;
    return;
}
Position FindPosition( List *L, ElementType Element)
{
    while (L->Element!=Element)
        L = L->Next;
    return L;
}







3.4
// given two sorted lists,L1 and L2,write a procedure to compute L1^L2 (L1 和L2的交集)
// using only the basic list operations.
void Write(List *L1, List* L2)
{
    Position l = *L1, p = *L2, TmpCell;
    List *L3;
    TmpCell = L3;
    while( l && p )
    {
        if( l->Element < p ->Element )
            l = l->Next;
        if ( l-> Element > p->Element )
            p = p->Next;
        if( l->Element == p->Element )
        {
            TmpCell->Element = l->Element;
            Position tmp = (Position*) malloc(sizeof (struct Node));
            if ( TmpCell == NULL )
            {
                printf("Out of space!\n");
                return L3;
            }
            TmpCell->Next = tmp;
        }
    }
    return L3;
}




3.15a
//write an array implementation of self-adjusting lists .
//A self-adjusting list is like a regular list, except that all insertions are performed at the front ,
//and when an element is accessed by a Find ,
//it is moved to the front of the list without changing the relative order of the other items.
struct Node
{
    ElementType Element;
    Position Next;
};
struct Node CursorSpace[SpaceSize];
for ( int i = 0; i < SpaceSize; i++)
{
    L[i].Element = 0;
    L[i].Next = (i+1) % SpaceSize;
}
void Insert(ElementType Element)
{
    Position p = Malloc();
    L[p].Element = Element;
    L[p].Next = L[0].Next;
    L[0].Next = p;
    return;
}
Position Malloc()
{
    int i = 0;
    while(L[i].Element)
        i++;
    return i;
}
void Find(ElementTYpe Element)
{
    int i = 0;
    while(L[L[i].Next].Element!=Element)
        i++;
    L[i].Next = L[L[i].Next].Next;
    i = L[i].Next;
    L[i].Next = L[0].Next;
    L[0].Next = i;
    return;
}




3.15b
// write a linked list implementation of self-adjusting lists.
void Insert(List *L, ElementType Element)
{
    Position p = (Position*)malloc(sizeof(struct Node));
    p->Element = Element;
    p->Next = L->Next;
    L->Next = p;
    return;
}
void Find(List *L, ElementType Element)
{
    Position p = L;
    while(p->Next->Element != Element)
        p = p->Next;
    Position tmp = p->Next;
    p->Next = tmp->Next;
    tmp->Next = L->Next;
    L->Next = tmp;
    return;
}




3.17
/*
an alternative to the deletion strategy we have given is to use lazy deletion .
To delete an element, we merely mark it deleted (using an extra bit field ).
the number of deleted and nondeleted elements in the list is kept as part of the data structure .
 if there are as many deleted elements as nondeleted elements, we traverse the entire list, 
 performing the standard deletion algorithm on all marked nodes.

   a. List the advantages and disadvantages of lazy deletion.

   b. write routines to implement the standard linked list operations using lazy deletion.
 */


//The advantage of lazy deletion is can save deletion time and is easy to implement.
//The disadvantage is wasting a lot of space.
struct Node
{
    Detected Deletion;//Deletion = 0 is deleted.
    ElementType Element;
    Position Next;
};
struct Node CursorSpace[SpaceSize];
//the head of List record the number of Deletions and the number of nondeleted.
//Head->Deletion = the number of deleted elements & Head->Element = the number of nondeleted elements.
void lazyDelet(List *L, ElementType Element)
{
    Position p = FindPrevious(L,Element);
    p->Deletion = 0;
    if(L->Deletion == L->Element)
    {
        L->Deletion = 0;
        p = L->Next;
        while(p && p->Deletion == 0)
        {
            Position tmp = p->Next;
            while(tmp && !tmp->Deletion) tmp = tmp->Next;
            if ( tmp )
            {
                p->Deletion = 1;
                tmp->Deletion = 0;
                p->Element = tmp->Element;
                tmp = p->Next;
                p->Next = tmp->Next;
            }
            else{
                p->Next = 0;
                break;
            }
        }
    }
    return;
}
Position FindPrevious( List *L, ElementType Element )
{
    Position p = L;
    while(p->Next->Element != Element && P->Next->Deletion)
        p = p->Next;
    return p;
}